package com.leetcode.solution.s8x;

import java.util.ArrayDeque;
import java.util.Deque;

public class MaximalRectangle85 {
    public static void main(String[] args) {
//        char[][] matrix = {
//                {'1', '0', '1', '0', '0'},
//                {'1', '0', '1', '1', '1'},
//                {'1', '1', '1', '1', '1'},
//                {'1', '0', '0', '1', '0'}
//        };

        char[][] matrix = {
                {'0','1'},
                {'1','0'}
        };

        int area = new MaximalRectangle85().maximalRectangle(matrix);
        System.out.println(area);
    }

    public int maximalRectangle(char[][] matrix) {
        int row = matrix.length;
        if (row == 0) {
            return 0;
        }

        int col = matrix[0].length;
        int[] height = new int[col];

        int area = 0;
        for ( int currRow = 0; currRow < row; currRow++) {
            for ( int currCol = 0; currCol < col; currCol++) {
                if (matrix[currRow][currCol] == '1') {
                    height[currCol]++;
                } else {
                    height[currCol] = 0;
                }

            }
            area = Math.max(area, largestRectangleArea(height));
        }

        return area;
    }

    public int largestRectangleArea(int[] heights) {
        if (heights.length == 0) {
            return 0;
        } else if (heights.length == 1) {
            return heights[0];
        }

        int[] newHeights = new int[heights.length + 2];
        for (int i = 0; i < heights.length; i++) {
            newHeights[i + 1] = heights[i];
        }

        heights = newHeights;
        Deque<Integer> heightStack = new ArrayDeque<>();
        heightStack.addLast(0);
        int res = 0;
        for (int idx = 1; idx < heights.length; idx++) {
            while (heights[idx] < heights[heightStack.peek()]) {
                int currIdx = heightStack.pop();

                res = Math.max(res, heights[currIdx] * (idx - heightStack.peek() - 1));
            }

            heightStack.push(idx);
        }

        return res;
    }
}
